class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // step1: 找到该行 matrix[i][0] <= target
        // step2: 找到该列 matrix[i][left] >= target, matrix[i][right] <= target
        // left > right ? false : true;
        if (matrix[0][0] > target || matrix[matrix.length - 1][matrix[0].length - 1] < target) {
            return false;
        }
        int left = -1;
        int right = matrix.length - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (matrix[mid][0] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        int row = right;
        left = 0;
        right = matrix[0].length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (matrix[row][mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        int start = right;
        left = -1;
        right = matrix[0].length - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (matrix[row][mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        int end = right;
        return start <= end;
    }
}
